\section{Ejercicio 3}
\subsection{Introducci'on}
\setlength{\parindent}{2em}
Dado un conjunto de personas, el ejercicio pide encontrar 2 grupos de tres personas cada uno:
\begin{itemize}
 \item Coppersmith(para nosotros David): las personas se conocen entre s'i.
 \item Winograd(para nosotros Jacobo): las personas no se conocen entre s'i.
\end{itemize}
Se conoce de antemano si 2 personas son amigos o no.\\
Para resolver este problema decidimos modelarlo con grafos, en donde:
\begin{itemize}
 \item Aristas: relaci'on de amistad entre las personas.
 \item Nodos: personas, numeradas de 1 hasta n para diferenciarlas.
\end{itemize}
Luego de modelarlo as'i, el problema se reduce a buscar un \textbf{$K_3$} en el grafo y su complemento, aquel que cumple que es el menor lexicogr'aficamente respecto de los restantes grupos.\\
Notar que se asume que la relaci'on de amistad es sim'etrica, por lo que se usa un grafo indireccionado.
Veamos m'as claramente lo que se pretende obtener, mediante un ejemplo: \\
\begin{figure}[H]
	\centering
		\includegraphics[width=0.4\textwidth]{dibujitos/david1.png}
	\caption{Grafo que reprensenta los grupos de personas relacionadas entre s'i}
\end{figure}
Primero vemos, dado el anterior grafo, los grupos de 3 personas relacionados entre s'i, o sea un tri'angulo(\textbf{$K_3$}): \\ 
\begin{figure}[H]
	\centering
		\includegraphics[width=0.5\textwidth]{dibujitos/david2.png}
	\caption{Las tres \textbf{$K_3$} hallados del grafo original}	
\end{figure}
De los 3 grupos hallados, debemos obtener aquel de menor orden lexicografico, y este es: \textbf{AFG}. Con lo cual este 'ultimo ser'a el grupo \textbf{David}(Coppersmith).\\
\newpage
Ahora veamos la pinta del complemento del grafo, para as'i, poder hallar el grupo \textbf{Jacobo} (Winogrand), si es que existe:\\
\begin{figure}[H]
	\centering
		\includegraphics[width=0.4\textwidth]{dibujitos/jacobo1.png}
	\caption{Grafo que reprensenta los grupos de personas relacionadas entre s'i}
\end{figure}
Sobre 'este, realizamos el mismo procedimiento de b'usqueda para encontrar grupos de 3 personas relacionados entre s'i en el complemento, o sea un tri'angulo(\textbf{$K_3$}): \\ 
\begin{figure}[H]
	\centering
		\includegraphics[width=0.5\textwidth]{dibujitos/jacobo2.png}
	\caption{Las cuatro \textbf{$K_3$} hallados del grafo complemento}	
\end{figure}

La complejidad esperada para determinar ambos grupos debe ser estrictamente menor que O(\textbf{$n^3$}).\\

\newpage

\subsection{Soluci'on}
Un algoritmo trivial buscar'ia todas las posibles combinaciones de grupos de tres personas sobre el total de personas, o sea, analizando todas las posiblidades, es decir, $\binom{n}{3}$ posibilidades, siendo n la cantiadad de nodos del grafo circular. Obteniendo de esta manera una complejidad acotada por O($n^3$):\\
( $\frac{n(n-1)(n-2)(n-3)!}{3!(n-3)!}$ =  $\frac{n(n-1)(n-2)}{3!}$ $\leq$ $n^3$).\\
Dado que esta complejidad no alcanza a lograr el objetivo pedido, seguimos buscando m'as y mejores ideas(respecto a eficiencia).\\
El algoritmo que se nos ocurri'o en un principio fue recorrer el grafo y por cada nodo chequear en los vecinos de los vecinos para saber si ese nodo con alg'un vecino forma un $K_3$(un circuito de grado 3). Esto lo logramos utilizando DFS, Depth-first search, una b'usqueda en profundidad sobre el grafo. Usando este algoritmo, la complejidad obtenida fue O($n * (n + m)$) en el caso que el grafo sea denso (con abundancia de ejes), esto tampoco consigue lograr la eficiencia pedida.\\
Finalmente decidimos usar el teorema visto en clase referente a la multiplicaci'on de la matriz de adyacencia. El teorema dice lo siguiente:\\
\newline
\textbf{\fbox{Teorema:}}\\
\newline
Si \textbf{A} es la matriz de adyacencia del grafo \textbf{G}, el elemento $a_{ij}^k$ de $A^{k}$ es igual a la cantidad de caminos de longitud $k$ entre i y j.\\
En nuestro caso nos interesan los elementos de la diagonal ($a_{ii}$) de $A^3$ ya que representan la cantidad de caminos de longitud 3 que parten y regresan a ese elemento. De este planteo surgen 3 complicaciones:
\begin{itemize}
	\item Obtener la multiplicaci'on de manera m'as eficiente a la forma estandar, ya que esta 'ultima tiene una complejidad de O($n^3$), lo cual no satisface a'un los requerimientos de la c'atedra.
	\item Como obtener los menores(lexicogr'aficamente) grupos.
	\item Como obtener el grupo de David y el grupo de Jacobo.
\end{itemize}
Para mejorar la complejidad del algoritmo, usamos el algoritmo de Strassen para la multiplicaci'on de matrices, cuya complejidad es O($n^{\log_2(7)}$) $\approxeq$ O($n^{2.801}$). Ver \textsl{http://en.wikipedia.org/wiki/Strassen\_algorithm}\\
Para obtener los grupos menores simplemente recorremos la diagonal de la matriz resultante(\textit{$A^3$}), de menor a mayor(orden lexicogr'afico), y nos quedamos con el primer elemento distinto de 0, porque dicho elemento contiene al menos 1 camino de longitud 3 hacia s'i mismo(por el teorema enunciado). Luego recorremos cada uno de sus vecinos y por cada uno de estos sus vecinos para determinar un $K_3$.\\
Para obtener los 2 grupos decidimos usar un 'unico algoritmo que recorre primero el grafo y luego su complemento:
\begin{itemize}
	\item Recorrido del grafo para buscar el grupo David.
	\item Recorrido del complemento para buscar el grupo Jacobo.
\end{itemize}

Para el grupo de David las \textit{personas}(nodos) \textit{se conocen entre s'i}(estan relacionados), por lo que el conjunto de nodos y las relaciones no deber'ia ser otro que el original, le'ido del archivo de entrada. Para el caso del grupo Jacobo esto es diferente, porque los nodos no deben estar relacionados entre s'i, dada esta situaci'on decidimos utilizar el complemento del grafo original ya que nos da la facilidad de generar un grafo en el que los nodos que est'an relacionados entre s'i formando un $K_3$, no lo estaban en el grafo original, cumpliendo con la premisa del grupo de Jacobo, la cual era que no existe relaci'on entre estos 3 nodos(personas).\\
Como veremos en el item 3.5, con este algoritmo alcanzamos la complejidad deseada. 

\newpage

\subsection{Pseudoc'odigo}

\newcommand{\jacoboYDavid}{\ensuremath{\mbox{\sc jacoboYDavid}}}
	\begin{algorithm}[H]
		\caption{$\jacoboYDavid()$}\label{alg:jacoboYDavid}
			\medskip
			\begin{algorithmic}[1]
			\STATE matrizCompletada $\leftarrow$ completarMatriz(matrizAdyacencia) 
			\STATE Strassen(Strassen(matrizCompletada))
			\STATE int minNodoDavidYJacobo $\leftarrow$ getMinNodoParaTriangulo(matrizCompletada)		
			\STATE int[ ] vecinosDeDavidOJacobo $\leftarrow$ vecinitosDe$_{minNodoDavidYJacobo}$
			\STATE int[ ] amigosDavidYJacobo
			\FOR {(i : vecinosDeDavidOJacobo)} 
				\STATE Int[ ] vecinosDeVecinosDeDavidOJacobo $\leftarrow$ vecinosDe$_{i}$
 				\FOR{(j : vecinosDeVecinosDeDavidOJacobo)} 
					\STATE ordenarLexicograficamente(amigosDavidYJacobo,i,j)
				\ENDFOR
			\ENDFOR	
			\STATE devolver amigosDavidYJacobo
			\end{algorithmic}
	\end{algorithm}

\subsubsection{Explicaci\'on del Pseudoc'odigo}
La funci'on jacoboYDavid comienza agrandando la matriz de adyancencias hasta la potencia de dos m'as cercana. Luego aplica Strassen a esta nueva matriz dos veces. El fin de aplicar Strassen es para llegar a una matriz de grado tres porque sabemos que 'esta nos dir'a la cantidad de caminos de largo tres de un nodo a otro.\\
Luego, para encontrar un ciclo de 3 nodos, busca en la diagonal de la matriz para hallar un camino de longitud 3 de un nodo a s'i mismo. Ya que debemos encontrar el menor orden lexicogr'afico, busca el primer nodo de la diagonal que tenga, al menos, un camino de longitud tres, lo llamamos minNodoDavidYJacobo.\\
Una vez hallado 'este recorre los vecinos y los vecinos de sus vecinos, chuequeando adyancencias para buscar el menor ciclo entre ellos.\\
Por 'ultimo devuelve estos tres nodos encontrados.\\
Este mismo proceso lo realizamos dos veces, una para encontrar los amigos de David y otra para encontrar los amigos de Jacobo con los complementos de las matrices.\\ 

\newpage

\subsection{Complejidad}
Sea $n$ la cantidad de nodos del grafo:\\
Antes de analizar la fuci'on principal, hay que saber que usamos cuatro matrices: 

\begin{itemize}
  \item la matriz de adyacencia y su complemento. 
  \item la matriz de vecinos(pasada como achivo de entrada) y su complemento. 
\end{itemize}

Construir cada matriz tiene una complejidad de O($n^2$). Hacemos esto ya que con ambas matrices se nos facilita cononer los amigos de alg'un nodo y saber si dos nodos son adyecentes, con costo constante(O($1$)). Esto 'ultimo se debe a que es, simplemente, un indexado sobre una posci'on determinada de alguna de las matrices dependediendo de la informaci'on que se desee conocer.\\    
Pasemos a analizar la complejidad de jacoboYDavid:\\
Lo primero que hace la funci'on es agrandar la matriz de adyacencia hasta la primer potencia de dos mayor a $n$. Dado que dicha potencia ser'menor o igual a n (esto depende si n es o no par), podemos acotar el tama'no de la matriz extendida como $2 * n$, con lo cual su costo se puede estimar como O($ 2 * n$). La extenci'on de la matriz es necesaria para poder utilizar Strassen correctamente cuando la matriz tiene un tama'no que no es potencia de dos. \\ 
Entonces la complejidad de esta operaci'on se puede acotar como O($ 2 * n^{2}$), correspondiente a extender la matriz original en una nueva y copiar la matriz de adyacencia en esta nueva matriz m'as grande.\\
Luego aplica Straseen dos veces para obtener una matriz de grado 3. El costo de aplicar Strassen cada vez es de $n^{2,801}$. Entonces aplicarla dos veces tiene una complejidad de O($2 * n^{2,801}$).\\
Ahora encuentra el menor nodo para armar el tri'angulo que buscamos. Esta funci'on recorre la diagonal de la matriz de grado 3 buscando alguna posici'on que contenga un entero positivo($> 0$). En peor caso va a recorrer toda la diagonal, por lo tanto la complejidad de buscar el menor nodo para el triangulo es O($n + u$), con $u$ lo que le faltaba a la matriz de adyacencia para completar hasta la potencia de $n$ m'as cercana. Como $u < n$, entonces podemos acotar la complejidad de buscar el menor nodo por O($2 * n$).\\ 
Si se encuentra alg'un nodo pertenciente a un circuito de grado 3, o sea, un elementos de la diagonal de la matriz no nulo y positivo, llamemoslo $v$, se empieza a recorrer los vecinos de $v$ y los vecinos de los vecinos de $v$, ambas en tiempo constante debido a que lo almacenamos en un arreglo de listas, con el fin de hallar el mencionado circuito. Esto se realiza mediante dos ciclos de repetici'on de 1 hasta la $\# amigos(v)$. En peor caso cada nodo puede a todos los dem'as como amigos(en el contexto de grafos, propiamente dicho, vecinos o adyacentes), produciendo un grafo extremadamente denso o, peor a'un, completo. Considerando esto podemos acotar esta busqueda como O($n^2$).\\
Adem'as llamamos a la funci'on jacoboYDavid 2 veces, la primera vez para encontrar encontrar el grupo Copersmith, y la segunda usando el complemento de las matrices para encontrar, de la forma descrita anteriormente aplicada al nuevo grafo, el grupo Winograd.\\
Considerando todo esto lo mencionado anteriormente, veamos la complejidad en conjunto:  
\begin{itemize}
  \item Generar las 4 matrices iniciales, O($4 * n^2$)
  \item Veamos DavidYJacobo:
  \begin{itemize}
    \item Extender la matriz de adyancencia, O($2 * n^{2}$)
    \item Aplicar la multiplicaci'on con strassen dos veces, O($2 * n^{2.801}$)
    \item Obtener el minNodoDavidYJacobo, O($2 * n$)
    \item Realizar la busqueda del(o los) k3, O($n^{2}$)
  \end{itemize}
\end{itemize}
Ahora bien, obtengamos la cota final: \\
\newline
O($4 * n^2$) + O($2 * (2 * n^{2} + 2 * n^{2,801} + 2 * n + n^{2})$) = \\
O($4 * n^2$) + O($4 * n^{2,801} + 5 * n^{2} + 4 * n$) $\in$ \fbox{\textbf{O($n^{2,801}$)}}, siendo esta la complejidad final conseguida.

\newpage

\subsection{Gr\'aficos}
 Esta secci'on tiene como objetivo analizar emp'iricamente la complejidad del algoritmo propuesto. No tiene sentido analizar un peor caso ya que la complejidad te'orica est'a acotada por la del algoritmo de Strassen que se realiza en todos los casos. Tiene m'as sentido analizar la entrada, si la cantidad de nodos es potencia de 2, si son grafos completos o no, la densidad de los grafos, etc.

\begin{figure}[h]
	\centering
		\includegraphics[width=0.8\textwidth]{graficos/ej3/operacioneshasta200aleatorios.png}
\end{figure}

\begin{itemize}
	\item M'aximo de 200 nodos
	\item Densidad de aristas del 50\%
	\item Relaciones aleatorias
\end{itemize}
En este caso se puede ver como la complejidad calculada est'a acotada siempre por:
\begin{itemize}
	\item Superiormente O($10 * n^{2,801}$)
	\item Inferiormente $\Omega$($n^{2,801}$)
\end{itemize}
La forma escalonada se debe al cambio de potencia de 2. El algoritmo busca la potencia de 2 mas cercana para completar la matriz por lo que hasta que no se supera la potencia de 2 mas cercana la complejidad se mantiene uniforme. La recta diagonal que une los escalones se debe a la interpolaci'on por la variaci'on en la cantidad de nodos para cada caso, en este ejemplo 19, es decir, entre cada caso de prueba hay 19 nodos de diferencia.
\newpage
\begin{figure}[h]
	\centering
		\includegraphics[width=0.8\textwidth]{graficos/ej3/operacioneshasta512potDe2Aletaorios.png}
\end{figure}

\begin{itemize}
	\item M'aximo de 512 nodos, solo potencias de 2
	\item Densidad de aristas del 50\%
	\item Relaciones aleatorias
\end{itemize}
En este caso se puede ver como la complejidad calculada est'a acotada superiormente O(10 x $n^{2,801}$).
La forma escalonada ya no est'a presente en este gr'afico, porque los casos son potencias de 2.
\newpage
\begin{figure}[h]
	\centering
		\includegraphics[width=0.8\textwidth]{graficos/ej3/operacioneshasta512potDe2AletaoriosCompAlgo.png}
\end{figure}

\begin{itemize}
	\item M'aximo de 512 nodos, solo potencias de 2
	\item Densidad de aristas del 50\%
	\item Relaciones aleatorias
\end{itemize}
En este caso se puede ver como la complejidad calculada est'a acotada superiormente por la complejidad del algoritmo trivial(O($n^3$)). A partir de los 100 nodos la diferencia es notable. La escala logar'itmica en el eje y permite ver la difencia y el crecimiento de la funci'on con mayor claridad.
\newpage
\subsection{Conclusi\'on}
\begin{itemize}
\item Fue ecencial usar multiplicaci'on de matrices para determinar la cantidad de caminos entre los pares de nodos del grafo.
\item El usar la multiplicaci'on de matrices mediante el algoritmo de Strassen con una complejidad  O($n^{2,801}$) nos permite lograr la complejidad requerida del algoritmo.
\item El algoritmo encuentra la soluci'on de manera m'as eficiente que usando fuerza bruta que ser'ia chequear todas las combinaciones de 3 nodos.
\end{itemize}
